|
|
Main menu for Browse IS/STAG
Course info
KIV / ZEP-E
:
Course description
Department/Unit / Abbreviation
|
KIV
/
ZEP-E
|
Academic Year
|
2023/2024
|
Academic Year
|
2023/2024
|
Title
|
Basics of effective programming
|
Form of course completion
|
Exam
|
Form of course completion
|
Exam
|
Accredited / Credits
|
Yes,
4
Cred.
|
Type of completion
|
Written
|
Type of completion
|
Written
|
Time requirements
|
Lecture
2
[Hours/Week]
|
Course credit prior to examination
|
Yes
|
Course credit prior to examination
|
Yes
|
Automatic acceptance of credit before examination
|
No
|
Included in study average
|
YES
|
Language of instruction
|
English
|
Occ/max
|
|
|
|
Automatic acceptance of credit before examination
|
No
|
Summer semester
|
0 / -
|
44 / -
|
4 / -
|
Included in study average
|
YES
|
Winter semester
|
0 / -
|
0 / -
|
0 / -
|
Repeated registration
|
NO
|
Repeated registration
|
NO
|
Timetable
|
Yes
|
Semester taught
|
Summer semester
|
Semester taught
|
Summer semester
|
Minimum (B + C) students
|
10
|
Optional course |
Yes
|
Optional course
|
Yes
|
Language of instruction
|
English
|
Internship duration
|
0
|
No. of hours of on-premise lessons |
|
Evaluation scale |
1|2|3|4 |
Periodicity |
každý rok
|
Evaluation scale for credit before examination |
S|N |
Periodicita upřesnění |
|
Fundamental theoretical course |
No
|
Fundamental course |
Yes
|
Fundamental theoretical course |
No
|
Evaluation scale |
1|2|3|4 |
Evaluation scale for credit before examination |
S|N |
Substituted course
|
None
|
Preclusive courses
|
KIV/ZEP
|
Prerequisite courses
|
N/A
|
Informally recommended courses
|
N/A
|
Courses depending on this Course
|
N/A
|
Histogram of students' grades over the years:
Graphic PNG
,
XLS
|
Course objectives:
|
Students should master the basic principles used in the design of efficient and robust algorithms. The course completes the set of bachelor study courses: KIV/PPA and KIV/ADT (or KIV/PPA1, KIV/PPA2, KIV/PT and KIV/PRO, alternatively). It is taught in English.
|
Requirements on student
|
Semester:
Four assignments including both theoretical exercises (e.g., design an effective algorithm that decides if there is no duplicity in the input array of integers) and practical (e.g., create a program that calculates the square root of two with 100 digits accuracy) are released during the semester. Each assignment is evaluated by at least 20 points. The student must collect at least 50 points to pass the course.
Exam:
Written test in which the student designs a method (algorithm) to solve a more complex problem. The test is evaluated by 20 points and these points are summed with points from the semester. Hence, the student can collect 100 points all in all. Marks are as follow:
1 = 86 - 100, 2 = 71 - 85, 3 = 56 - 70, 4 = < 55 points
|
Content
|
- The evaluation of algorithms, time and memory complexity. Master theorem.
- Common redundant, time-consuming operations in the code and their elimination.
- The robustness of algorithms, singular cases, and the accuracy of numerical calculations.
- Matrix and vector operations (Strassen formula, dot and cross product). Linear and non-linear systems of equations (including overdetermined systems).
- Memory management. Memory allocation, deallocation, garbage collector, memory leaks. Too large data sets (they do not fit the memory).
- Cache in the current computers and its efficient use (bricking technique)
- Divide and Conquer. Binary vs. interpolation search, median. Space partitioning.
- Big data processing. Reduction of problem space dimension. Data sampling, Sobolov sequences. Custom SW cache. Compression. Checksums (LUHN, CRC, Adler32, MD5).
- Graph representations, Dijkstra and Floyd-Warshall algorithms.
- Heuristics approach. State machines, pruning. The problem of optimal assignment - Hungarian marriage.
|
Activities
|
|
Fields of study
|
Předmět má vedené stránky na CourseWare (https://courseware.zcu.cz/portal/studium/courseware/kiv/zep-e), kde jsou pro studenty k dispozici kompletní prezentace z přednášek, a to jak v angličtině, tak češtině (pro studenty, kteří by měli problém s úrovní angličtiny).
Pro předmět dále existuje zřízený Discord server ZEP-E (pozvánka je rozesílána zapsaným studentům před zahájením semestru), kde studenti mezi sebou nebo s vyučujícími mohou řešit problémy s řešením semestrální práce, ale i diskutovat zkouškové příklady apod. Odezvy od vyučujících jsou do 24 hodin, většinou "okamžité".
|
Guarantors and lecturers
|
|
Literature
|
|
Time requirements
|
All forms of study
|
Activities
|
Time requirements for activity [h]
|
Individual project (40)
|
40
|
Preparation for an examination (30-60)
|
30
|
Contact hours
|
26
|
Total
|
96
|
|
Prerequisites
|
Knowledge - students are expected to possess the following knowledge before the course commences to finish it successfully: |
describe computer program execution |
describe the principles of imperative programming, i.e., control flow, methods, etc. |
be familiar with mathematical concepts at the level of secondary school mathematics |
Skills - students are expected to possess the following skills before the course commences to finish it successfully: |
create a computer program in any programming language to solve a simple problem (e.g., deciding whether there are duplicities in an array of numbers) |
Competences - students are expected to possess the following competences before the course commences to finish it successfully: |
N/A |
|
Learning outcomes
|
Knowledge - knowledge resulting from the course: |
assessment of time and memory complexity of both recursive and non-recursive programs |
basic principles used in the design of the effective algorithms (such as sorting, divide & conquer, space partitioning) |
basic principles used to increase the effectivity or robustness of concrete implementation (e.g., elimination of constant calculations in loops, data alignment to better fit the cache, data compression, etc.) |
Skills - skills resulting from the course: |
design of an algorithm solving a non-trivial problem (such as optimal choice of supermarkets in a city) |
assess the expected algorithmic complexity of the designed algorithm |
Competences - competences resulting from the course: |
N/A |
|
Assessment methods
|
Knowledge - knowledge achieved by taking this course are verified by the following means: |
Written exam |
Seminar work |
Skills - skills achieved by taking this course are verified by the following means: |
Written exam |
Seminar work |
Competences - competence achieved by taking this course are verified by the following means: |
Written exam |
Seminar work |
|
Teaching methods
|
Knowledge - the following training methods are used to achieve the required knowledge: |
Interactive lecture |
Individual study |
One-to-One tutorial |
Seminar classes |
Skills - the following training methods are used to achieve the required skills: |
Interactive lecture |
Individual study |
Competences - the following training methods are used to achieve the required competences: |
Interactive lecture |
Discussion |
One-to-One tutorial |
|
|
|
|